package search;

import java.util.ArrayList;
import java.util.List;

public class InsertValueSearch {
    public static void main(String[] args) {

    }

    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        //将mid变成另一种形式
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        if (findVal > arr[mid]) {
            return insertValueSearch(arr, mid + 1, right, findVal);
        } else if (findVal < arr[mid]) {
            return insertValueSearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
    public static List<Integer> insertValueSearchPlus(int[] arr, int left, int right, int findVal) {
        List<Integer> list = new ArrayList<>();
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return list;
        }
        //将mid变成另一种形式
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        if (findVal > arr[mid]) {
            return insertValueSearchPlus(arr, mid + 1, right, findVal);
        } else if (findVal < arr[mid]) {
            return insertValueSearchPlus(arr, left, mid - 1, findVal);
        } else {
            //不是用递归，而是使用while循环进行添加。要知道，它是有序的啊！，而且递归确实也做不了
            //1、左扫描
            return findOtherSame(mid, list, findVal, arr);
        }
    }

    /**
     * 查找其他一样的数，并获取下标给list
     * @param mid
     * @param list
     * @param findVal
     * @param arr
     * @return
     */
    public static List<Integer> findOtherSame(int mid, List<Integer> list,int findVal,int[] arr) {
        int temp = mid;
        while (temp >= 0 && arr[temp] == findVal) {
            list.add(temp);
            temp--;
        }
        //2、右扫描
        while (temp <= arr.length-1 && arr[temp] == findVal) {
            list.add(temp);
            temp++;
        }
        return list;
    }
}
